package algorithm.linkedlist;

import algorithm.model.ListNode;

/**
 * leetcode : https://leetcode.com/problems/linked-list-cycle-ii/description/
 * Difficulty : Medium
 *
 * 给一个链表，判断链表是否有环。
 * 如果有环，返回环开始的节点。否则返回null
 *
 * 不用额外的空间解决问题
 *
 * 思路还是快慢指针，但是快慢指针相遇时只能说明有环并且在环内相遇
 * 难点在于找到起点
 *
 * 参考思路：
 * https://blog.csdn.net/lalor/article/details/7628332
 *
 * @Author Antony
 * @Since 2018/7/23 19:57
 */
public class LinkedListCycleII {

    public static void main(String[] args) {
        // 环的起点是3
        ListNode initNode = ListNode.initDate(new int[]{1,2,3});
        ListNode nextNode = ListNode.initDate(new int[]{4,5});
        initNode.next.next.next = nextNode;
        nextNode.next.next = initNode.next.next;

        System.out.println(detectCycle(initNode).val);
    }


    /**
     * beats 100.0% - 0ms
     *
     * 思路：
     * 第一次相遇后，说明有环，
     * 这时候把慢指针拉回head，再让两个指针都以步长1走一遍
     * 再一次相遇的时候，就是环的起点
     */
    public static ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        boolean meet = false;
        while(fast != null && fast.next != null && slow != null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                meet =  true;
                slow = head;
                break;
            }
        }
        while(meet){
            if(fast == slow) return slow;
            fast = fast.next;
            slow = slow.next;
        }

        return null;
    }
}
